Most computers and many electronic devices include a processor and a memory. The processor usually executes instructions and performs various operations on data. The instructions and data are usually obtained from the memory. The processor may also save data to the memory. Thus, the speed of communications between the processor and the memory is a very important factor contributing to the overall speed of the system.
Cache is a type of memory used to improve the speed of processor to memory communication. Cache memory is usually provided in addition to the ordinary or main memory of a computer or electronic device. Cache memory usually provides for much faster access to/from the processor than ordinary memory. Thus, the cache memory is usually placed in physical proximity to the processor, may be connected to the processor through a wider or faster connection, and may be configured for faster internal operation (e.g., higher clock rate). However, these benefits usually involve a trade-off-cache memory is usually more expensive than the main memory, and usually only a small amount of cache memory (as compared to the main memory) may be practicably used.
One intended purpose of cache memory is to temporarily hold data and/or instructions of the main memory which the processor is currently using. Thus, the processor may perform most memory access by communicating with the cache, which is faster than communicating with the main memory. Meanwhile, memory control logic may selectively load various values from memory to the cache and store various values of the cache back into main memory.
Usually, cache memory systems are designed to be invisible to the software running at the processor. Thus, they are designed so that the software itself does not have to load/store data to the cache/main memory, or keep track of whether certain data is in the cache or the main memory. Instead, the software usually addresses all data and instructions as if they are in main memory, and various cache controller electronics keep track of whether the data being accessed is in the cache, whether it should be moved to the cache and whether it should be stored into memory. Furthermore, cache systems are usually designed to be software independent as well. The above features are considered desirable for most systems in order to ensure processor/software independence. This may in turn provide for a wider degree of compatibility between different processors and different pieces of software.
Many complex systems have been designed in order to provide optimal cache operation. In general a cache controller will greatly improve the speed of the processor, if it can correctly predict what data will be used by the processor and keep that data in the cache. This, however, is a difficult task. As noted above, the size of the cache is limited in comparison to the main memory and thus the controller must be selective as to which data should be loaded into the cache.
If the processor attempts to access a memory address, the processor usually first checks the cache to determine if the memory address is already cached (i.e., a copy is stored in the cache). If that is the case then the processor may access the address relatively quickly from the cache. This result is referred to as a cache hit. If that is not the case, the processor must access the address at the main memory—a much more time intensive operation. This is referred to as a cache miss. In the case of a cache miss, the accessed memory address is usually loaded into the cache (often a block of adjacent memory is also loaded). This is done because often if the processor attempts to access a certain address, this is an indication that it will probably access that same address or other addresses adjacent to it again in the near future.
If the controller determines that a new block of data needs to be stored in the cache but the cache is already full, then the controller must remove or evict an existing block of data. However, doing so may actually decrease performance if the data block being evicted will be actually used more often by the processor in the immediate future than the new data block being added. Thus, many controllers use complex replacement algorithms to determine which blocks are to be left in the cache and which blocks are to be evicted to make space for the new blocks.
If the controller is not accurate at predicting which memory addresses will be accessed by the processor in the future and consequently does not keep these addresses in the cache, then the processor would likely experience a high number of misses. This would result in sharply decreased performance as the main memory would have to be accessed numerous times. This situation is often referred to as cache pollution, as it implies that a large number of useless entries (i.e., entries that are not often used by the processor) are being kept in the cache. The same situation is also some times referred to as cache thrashing as it often involves frequent loading and replacing of data into the cache as each cache miss causes new data to be loaded into the cache.
In practice, cache pollution often results when useful data blocks (i.e., data blocks that will be accessed by the processor often in the near future) are evicted from the cache to make room for relatively useless data blocks (i.e., ones that will not be accessed often in the near future).
However, it is difficult for a cache controller to predict which data block is useful and which useless. The cache controller is not aware of the future behavior of the processor. Thus, many existing cache controllers evict data blocks based on the time these data blocks were initially placed in the cache or the time they were last used by the processor. The software running on the processor may possess more accurate information as to which blocks of data are likely to be used by that software in the near future. But most existing systems do not allow this information to be used for cache management as the cache system is intended to be invisible to the software and not dependent on the software.
What is needed is a system which reduces cache pollution by better predicting which data blocks will be more or less frequently used by the processor in the near future. Further needed is a system that ensures that relatively useful data blocks will not be replaced in the cache by relatively useless data blocks.